#include <iostream>
#include <list>
#include <cstdlib>

using namespace std;
struct Node
{
    int pos = 0;
    int key = 0;
    int next = 0;
};

void print(Node& x)
{
    printf("%05d, %d, %05d\n", x.pos, x.key, x.next);
}
void updateList(list<Node>& lt)
{
    if (lt.empty())
        return;
    auto cur = lt.begin();
    auto second = lt.begin();
    ++second;
    while (second != lt.end())
    {
        cur->next = second->pos;
        ++cur;
        ++second;
    }
    cur->next = -1;
}
void print(list<Node> lt)
{
    if (lt.empty())
        return;
    auto cur = lt.begin();
    while (cur != --lt.end())
    {
        printf("%05d %d %05d\n", cur->pos, cur->key, cur->next);
        ++cur;
    }
    printf("%05d %d %d\n", cur->pos, cur->key, cur->next);
}

int main()
{
    // 输入开始地址和节点个数
    int position, n;
    cin >> position >> n;

    // 创建数组存储节点并便于查找
    Node* table = new Node[100000];

    // 输入节点信息
    for (int i = 0; i < n; ++i)
    {
        Node tmp;
        cin >> tmp.pos >> tmp.key >> tmp.next;
        table[tmp.pos] = tmp;
        // print(table[tmp.pos]);
    }

    // 构建链表res和reject
    // 一个数组记录是否有重复
    int* record = new int[10001]{ 0 };
    list<Node> res, reject;
    while (position != -1)
    {
        // cout << position << ' ';
        int offset = abs(table[position].key);
        if (record[offset] == 0)
        {
            res.push_back(table[position]);
            record[offset] = 1;
        }
        else
        {
            reject.push_back(table[position]);
        }
        position = table[position].next;
    }
    /*
    cout << endl;
    print(res);
    cout << endl;
    print(reject);
    */
    // 调整链表
    updateList(res);
    updateList(reject);
    print(res);
    print(reject);
    

    delete[] table;
    delete[] record;
    return 0;
}
